/*
 * doubly_conc_ll.c
 *
 *  Created on: May 27, 2012
 *      Author: Itamar
 */
#include <assert.h>
#include <pthread.h>
#include <stdlib.h>
#include "doubly_conc_ll.h"
#include "read_write_mayWrite_lock.h"
#include "hw3_helpers.h"

/* Structs Definitions */
typedef struct node_t {
	struct node_t* prev;
	struct node_t* next;
	int key;
	char data;
	bool deleted;
	RWMW_Lock node_lock;
} *Node;

typedef struct dcll_t {
	Node head;
	Node tail;
} *DConc_LL;

typedef struct dqnode_t {
	struct dqnode_t* next;
	Node node;
} *dqNode;

typedef struct delq_t {
	dqNode head;
	dqNode tail;
	pthread_mutex_t queue_lock;
} *DeletedQueue;

/* Global Variables */
DConc_LL ll;
DeletedQueue dq;
/* Local Functions */

/* ============= Helper Functions ============= */

Node create_dcll_node(int key, char data, Node prev,Node next) {
	Node tmp = malloc(sizeof(struct node_t));
	if (tmp==NULL) return NULL;
	tmp->node_lock = init_lock();
	if (tmp->node_lock==NULL) {
		free(tmp);
		return NULL;
	}
	tmp->key=key;
	tmp->data=data;
	tmp->deleted=false;
	tmp->next=next;
	tmp->prev=prev;
	return tmp;
}

void destroy_dcll_node(Node node) {
	if (node==NULL) return;
	destroy_lock(node->node_lock);
	free(node);
	return;
}

void enqueue_dq_node(Node node) {
	dqNode tmp = malloc(sizeof(struct dqnode_t));
	if (tmp==NULL) return;
	tmp->node = node;
	tmp->next=NULL;
	pthread_mutex_lock(&dq->queue_lock);
		if(!dq->tail) {
			dq->head=tmp;
			dq->tail=tmp;
		} else {
			dq->tail->next=tmp;
			dq->tail=tmp;
		}
	pthread_mutex_unlock(&dq->queue_lock);
	return;
}

/*
 * Going over the list in the from the higher keys to the lower until
 * reaching its end or finding a key which is smaller or equel the given key
 */
Node insert_tail_aux_move_left(Node it, int key){
	while ((it->key != 0) && (it->key > key)) {
		it = it->prev;
	}
	return it;
}
/*
 * The function finds the location where the new node should be inserted.
 * if in the process, the function finds a node with the given key,
 * or memory allocation failed, false will be returned. otherwise the node
 * will be inserted and true will be returned.
 * Note - "start" should already be locked as may_write and will be freed
 * by this function when needed.
 */
bool insert_right(Node start, int key, char data) {
	Node next = start->next;
	get_may_write_lock(next->node_lock);
	while ((next != ll->tail) && (next->key < key)) {
		// this is not the right node and also not the last one
		release_shared_lock(start->node_lock);
		start = next;
		next = start->next;
		get_may_write_lock(next->node_lock);
	}
	Node new_node = create_dcll_node(key, data, start, next);
	if ((!new_node) || next->key == key) {
		// memory allocation failed or a node with that key already exists
		destroy_dcll_node(new_node);
		release_shared_lock(start->node_lock);
		release_shared_lock(next->node_lock);
		return false;
	}
	upgrade_may_write_lock(start->node_lock);
	upgrade_may_write_lock(next->node_lock);
	start->next = new_node;
	next->prev = new_node;
	release_exclusive_lock(start->node_lock);
	release_exclusive_lock(next->node_lock);
	return true;
}

/* ============= Interface Functions Implementation ============= */

void Initialize() {
	ll = malloc(sizeof(struct dcll_t));
	if (ll==NULL) return;
	dq = malloc(sizeof(struct delq_t));
	if (dq == NULL) {
		free(ll);
		return;
	}
	ec_mutex_init(&dq->queue_lock);
	dq->head=NULL;
	dq->tail=NULL;
	ll->head=create_dcll_node(0,'0',NULL,NULL);
	ll->tail=create_dcll_node(0,'0',ll->head,NULL);
	ll->head->next=ll->tail;
	return;
}

void Destroy() {
	Node node = ll->head;
	while (node) {
		Node del = node;
		node = node->next;
		destroy_dcll_node(del);
	}
	ClearDeleted();
	pthread_mutex_destroy(&dq->queue_lock);
	free(dq);
	free(ll);
	return;
}

// list structure is: 0 is always first, all other nodes are sorted after it (also negatives)
bool InsertHead(int key, char data) {
	Node first = ll->head;
	get_may_write_lock(first->node_lock);
	//shouldn't happen, but checking
	if (first->key == key) {
		assert(0);
		release_shared_lock(first->node_lock);
		return false;
	}
	return insert_right(first, key, data);
}

bool InsertTail(int key, char data) {
	bool insert_to_right = false;
	if (key == 0) {
		return false;
	}
	Node it = ll->tail;
	while (!insert_to_right) {
		it = insert_tail_aux_move_left(it->prev, key);
		get_may_write_lock(it->node_lock);
		if (it->deleted == false) {
			insert_to_right = true;
		} else {
			release_shared_lock(it->node_lock);
		}
	}
	if (it->key == key) {
		// key already exists
		release_shared_lock(it->node_lock);
		return false;
	}
	// releasing the lock is taking care of in this function
	return insert_right(it, key, data);
}

bool Delete(int key) {
	Node first = ll->head;
	get_may_write_lock(first->node_lock);
	//shouldn't happen, but checking
	if (first->key == key) {
		assert(0);
		release_shared_lock(first->node_lock);
		return false;
	}
	Node second = first->next;
	get_may_write_lock(second->node_lock);
	//find the node to delete
	while (second != ll->tail && second->key != key) {
		release_shared_lock(first->node_lock);
		first=second;
		second=second->next;
		get_may_write_lock(second->node_lock);
	}
	//if the node wasn't found
	if (second == ll->tail) { 
		release_shared_lock(second->node_lock);
		release_shared_lock(first->node_lock);
		return false;
	}
	//if it was found
	if (second->key == key) {
		Node third = second->next;
		get_may_write_lock(third->node_lock);
		upgrade_may_write_lock(first->node_lock);
		upgrade_may_write_lock(second->node_lock);
		upgrade_may_write_lock(third->node_lock);
		first->next = third;
		third->prev = first;
		second->deleted=true;
		enqueue_dq_node(second);
		release_exclusive_lock(first->node_lock);
		release_exclusive_lock(second->node_lock);
		release_exclusive_lock(third->node_lock);
		return true;
	}
	assert(0);
	return false;
}

void ClearDeleted() {
	pthread_mutex_lock(&dq->queue_lock);
		dqNode tmp = dq->head;
		while (tmp) {
			dqNode toDel = tmp;
			destroy_dcll_node(tmp->node);
			tmp=tmp->next;
			free(toDel);
		}
		dq->head = NULL;
		dq->tail = NULL;
	pthread_mutex_unlock(&dq->queue_lock);
	return;
}

bool Search(int key, char* data) {
	if(key == 0) return false;
	Node first = ll->head;
	get_read_lock(first->node_lock);
	Node second = first->next;
	get_read_lock(second->node_lock);
	while(second != ll->tail && key != second->key) {
		release_shared_lock(first->node_lock);
		first = second;
		second = first->next;
		get_read_lock(second->node_lock);
	}
	// if we've reached the end of the list, the key doesnt exist
	// we release all locks and return false.
	if(second == ll->tail) {
		release_shared_lock(first->node_lock);
		release_shared_lock(second->node_lock);
		return false;
	}
	// we set data with the node's data, release all locks and return true.
	else {
		*data = second->data;
		release_shared_lock(first->node_lock);
		release_shared_lock(second->node_lock);
		return true;
	}
}

